500C - New Year Book Reading - CodeForces Solution


constructive algorithms greedy implementation math *1600

Please click on ads to support us..

Python Code:

n, m = map(int,input().split())
w = list(map(int, input().split())) + [0]
b = [(int(x)-1) for x in input().split()]
ans = 0
for i in range(m):
    for j in range(i-1,-1,-1):
        if b[j] == b[i]:
            b[j] = n
            break
        ans += w[b[j]]
print(ans)

C++ Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

 
const int maxn = 1e6 + 10;
const int MOD = 1e9+7;


int a[maxn], last[maxn], mark[maxn];

void solve(){

	int n, m;
	cin>> n>> m;
	

	for(int i = 0; i < n; i++){
		cin>> a[i + 1];
	}
	int x;
	cin>> x;
	
	vector<int>vec;
	vec.pb(x);
	
	for(int i = 1; i < m; i++){
		cin>> x;
		if(x != vec.back())	vec.pb(x);
	}
	
	int ans = 0;
	int sum = 0;
	int cnt = 1;
	for(int u: vec){
//if(last[u]) cout<<"||||||||||"<< u<< endl;
		int sum1 = 0;
		fill(mark, mark + n + 1, 0);
		for(int i = last[u]; i < cnt - 1; i++){
			if(!mark[vec[i]]){
				//if(!last[u]) cout<<a[vec[i]] <<" ";
				sum1+= a[vec[i]];
				mark[vec[i]] = 1;
			}
	
		}
		//cout<< endl;
		last[u] = cnt;
		ans += sum1;
		//cout<< sum1 << endl;
		cnt++;
	}
	cout<< ans ;
	
}
int main(){
	
	solve();
	return 0;	
}


Comments

Submit
0 Comments
More Questions

1622C - Set or Decrease
1682A - Palindromic Indices
903C - Boxes Packing
887A - Div 64
755B - PolandBall and Game
808B - Average Sleep Time
1515E - Phoenix and Computers
1552B - Running for Gold
994A - Fingerprints
1221C - Perfect Team
1709C - Recover an RBS
378A - Playing with Dice
248B - Chilly Willy
1709B - Also Try Minecraft
1418A - Buying Torches
131C - The World is a Theatre
1696A - NIT orz
1178D - Prime Graph
1711D - Rain
534A - Exam
1472A - Cards for Friends
315A - Sereja and Bottles
1697C - awoo's Favorite Problem
165A - Supercentral Point
1493A - Anti-knapsack
1493B - Planet Lapituletti
747B - Mammoth's Genome Decoding
1591C - Minimize Distance
1182B - Plus from Picture
1674B - Dictionary